#include <iostream>
#include <stack>

using namespace std;
// 20.有效的括号
//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
//有效字符串需满足：
//左括号必须用相同类型的右括号闭合。
//左括号必须以正确的顺序闭合。
//每个右括号都有一个对应的相同类型的左括号。
class Solution {
public:
    bool isValid(string s) {
        stack<char> st; // 定义一个栈容器st
        size_t n = s.size();  // 求字符串的长度n

        for(int i = 0; i < n; i++)
        {
            if(s[i] == '(' || s[i] == '[' || s[i] == '{')
                st.push(s[i]);    // 所有左括号进栈
            else {  // 遇到右括号
                if(st.empty()) // 栈空时返回false
                    return false;

                if(s[i] == ')' && st.top() != '(') return false;
                if(s[i] == ']' && st.top() != '[') return false;
                if(s[i] == '}' && st.top() != '{') return false;

                st.pop();
            }
        }
        return st.empty();  // 栈空，配对成功；栈不空，说明左括号多了
    }
};

int main() {
    std::cout << "Hello, World!" << std::endl;
    return 0;
}
